package com.platform.modules.alg.alglib.poj3468;

public class Poj3468 {
    public String output = "";
    private int N = 100010;
    private long a[] = new long[N];
    private long sum[] = new long[N];
    private long add[] = new long[N];
    private int L[] = new int[N];
    private int R[] = new int[N];
    private int d;
    private int pos[] = new int[N];
    int n;
    int m;
    int t;
    int l;
    int r;
    char op[] = new char[3];

    // 预处理
    void build() {
        t = (int) Math.sqrt(n * 1.0);
        int num = n / t;
        if (n % t != 0) num++;
        for (int i = 1; i <= num; i++) {
            // 每块的左右
            L[i] = (i - 1) * t + 1;
            R[i] = i * t;
        }
        R[num] = n;
        for (int i = 1; i <= num; i++)
            for (int j = L[i]; j <= R[i]; j++) {
                pos[j] = i; // 表示属于哪个块
                sum[i] += a[j]; // 计算每块和值
            }
    }

    // 区间[l,r]加上d
    void change(int l, int r, long d) {
        int p = pos[l], q = pos[r]; // 读所属块
        if (p == q) { // 在一块中
            for (int i = l; i <= r; i++) // 暴力修改
                a[i] += d;
            sum[p] += d * (r - l + 1); // 修改和值
        } else {
            for (int i = p + 1; i <= q - 1; i++) // 中间完全覆盖块打懒标记
                add[i] += d;
            for (int i = l; i <= R[p]; i++) // 左端暴力修改
                a[i] += d;
            sum[p] += d * (R[p] - l + 1);
            for (int i = L[q]; i <= r; i++) // 右端暴力修改
                a[i] += d;
            sum[q] += d * (r - L[q] + 1);
        }
    }

    // 区间查询
    long query(int l, int r) {
        int p = pos[l], q = pos[r];
        long ans = 0;
        if (p == q) { // 在一块中
            for (int i = l; i <= r; i++) // 累加
                ans += a[i];
            ans += add[p] * (r - l + 1); // 计算懒标记
        } else {
            for (int i = p + 1; i <= q - 1; i++) // 累加中间块
                ans += sum[i] + add[i] * (R[i] - L[i] + 1);
            for (int i = l; i <= R[p]; i++) // 左端暴力累加
                ans += a[i];
            ans += add[p] * (R[p] - l + 1);
            for (int i = L[q]; i <= r; i++) // 右端暴力累加
                ans += a[i];
            ans += add[q] * (r - L[q] + 1);
        }
        return ans;
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] nums = line[0].split(" ");
        n = Integer.parseInt(nums[0]);
        m = Integer.parseInt(nums[1]);
        String[] words = line[1].split(" ");

        for (int i = 1; i <= n; i++)
            a[i] = Integer.parseInt(words[i - 1]);
        build();
        for (int i = 1; i <= m; i++) {
            String[] command = line[i + 1].split(" ");
            l = Integer.parseInt(command[1]);
            r = Integer.parseInt(command[2]);

            if (command[0].charAt(0) == 'C') {
                d = Integer.parseInt(command[3]);
                change(l, r, d);
            } else
                output += query(l, r) + "\n";
        }
        return output;
    }
}
